/*
 * @lc app=leetcode.cn id=375 lang=typescript
 *
 * [375] 猜数字大小 II
 */

// @lc code=start
function getMoneyAmount(n: number): number {
  // dp[i][j]表示[i,j]范围内的最小现金数
  const dp = new Array(n + 1).fill(0).map((_) => new Array(n + 1).fill(0));

  // 正向无法查找到k+1结果，所有需要反向遍历
  for (let i = n - 1; i >= 1; i--) {
    for (let j = i + 1; j <= n; j++) {
      dp[i][j] = Number.MAX_SAFE_INTEGER;
      for (let k = i; k < j; k++) {
        // 以k为中间点，左右结果中取一个，然后取最小值
        dp[i][j] = Math.min(dp[i][j], k + Math.max(dp[i][k - 1], dp[k + 1][j]));
      }
    }
  }
  return dp[1][n];
}
// @lc code=end
